# 字节一面算法原题~~~ 血的教训
# 力扣： https://leetcode-cn.com/problems/generate-parentheses/
# 视频讲解，最符合面试官引导思路的：https://leetcode-cn.com/problems/generate-parentheses/solution/pei-yang-chou-xiang-si-wei-hui-su-jie-fa-7dwu/

"""
深度优先遍历：Depth First Search, 简称： DFS
广度优先遍历：Breadth First Search, 简称： BFS
"""

class Solution:
    def generateParenthesis(self, n: int):
        nums_list = []
        def generate(A, left, right):
            """
            param: A 代表当前 拼凑的组合
            param: left 左括号数量
            param: right 右括号数量
            """
            
            # 剪枝: 就这么多代码！！ 但是底层思路很重要~
            if left > n or left < right:
                return 

            # 全排列， 满足深度就退出
            if len(A) == 2*n:
                nums_list.append(A)
                return 

            generate(A + "(", left+1, right)
            generate(A + ")", left, right+1)
        
        generate("", 0, 0)
        return nums_list


s = Solution()
ans = s.generateParenthesis(4)
print(ans)


# 另外的实现
def generate1(A, left, right):
            """
            param: A 代表当前 拼凑的组合
            param: left 左括号数量
            param: right 右括号数量
            """

            # 全排列， 满足深度就退出
            if len(A) == 2*n:
                nums_list.append(A)
                return 

            # 剪枝的判断加到这里，更像是正常的去想一个递归的思路
            if left < n:
                generate(A + "(", left+1, right)
            if left > right:    
                generate(A + ")", left, right+1)

                